package tree

import "math"

func maxPathSum(root *TreeNode) int {
	maxSum := math.MinInt32
	var dfs func(node *TreeNode) int
	dfs = func(node *TreeNode) int {
		if node == nil {
			return 0
		}
		left := max(dfs(node.Left), 0)
		right := max(dfs(node.Right), 0)
		
		price := node.Val + left + right
		maxSum = max(maxSum, price)
		return node.Val + max(left, right)
	}
	dfs(root)
	return maxSum
}